package code.class4;

/**
 * https://leetcode.cn/problems/M1oyTv/description/
 * 最小覆盖子串
 * 解题思路：
 * 1.先把target字符计算出数量
 * 2.遍历字符串，当减完target的字符串长度后，进行缩减
 */
public class Code03_minWindow {
    public static void main(String[] args) {
        String str = "ADOBECODEBANC";
        String target = "ABC";
        // 输出："BANC"
        String s = minWindow(str, target);
        System.out.println("s = " + s);
    }

    public static String minWindow(String str, String target) {
        char[] sArr = str.toCharArray();
        char[] tArr = target.toCharArray();
        int[] cnt = new int[256];

        // 计算 target 每个字符 数量
        for (char c : tArr) {
            cnt[c]--;
        }

        /**
         * l 和 r 左右指针
         * len:窗口宽度
         * k:字符数
         * start:最小字符串开始位置
         */
        int l = 0, r = 0, len = Integer.MAX_VALUE, k = target.length(), start = 0;
        for (; r < str.length(); r++) {
            // 当匹配串存在 存储数组中<0,则说明该位置有子串字符
            /*
             * 另外本行是比较后需要对出现的字符进行++,因此可以拆成下面这种形式
             * if(cnt[sArr[r]]<0){
             *   k--
             * }
             * cnt[sArr[r]]++;
             */
            if (cnt[sArr[r]]++ < 0) {
                k--; // 总数量需要--
            }
            // 当k ==0 时，说明当前 l ~ r 的范围，包含了所有t字符串
            if (k == 0) {
                /**
                 * 1.当上面 cnt[sArr[l]]++ 后，这里自然会判断加进来的字符是否为target中的字符
                 *   如果是 target 中的字符，则数量--，同时 l 的位置右移
                 *   如果l移动的位置不是target中的字符，则 了继续 右移，直到移动到cnt[sArr[l]] == 0的位置
                 */
                while (cnt[sArr[l]] > 0) {
                    cnt[sArr[l]]--;
                    l++;
                }
                // 判断当前范围是否小于最大长度，重新修改起始位置和范围
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    start = l;
                }
            }
        }

        return len == Integer.MAX_VALUE ? "" : str.substring(start, start + len);
    }

}
